

public class Fib {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);

        long start = System.nanoTime();

        // compute fib using either the sequential or the parallel version
        //long result = seqFib(n);
        long result = parFib(n, 0);
        
        long time = System.nanoTime() - start;

        System.out.printf("Computing fib(%d) = %d took %f ms\n", n, result, time/1e6);
    }

    public static long seqFib(int n) {
        if (n < 2) {
            return n;
        } else {
            return seqFib(n-2) + seqFib(n-1);
        }
    }


    public static long parFib(int n, int depth) {
        if (n < 2) {
            return n;
        } else {
            if (depth > 3) {
                return seqFib(n);
            } else {
                FibTask f1 = new FibTask(n-2, depth+1);
                FibTask f2 = new FibTask(n-1, depth+1);
                
                Thread t1 = new Thread(f1);
                Thread t2 = new Thread(f2);
                t1.start();
                t2.start();
                try {
                    t1.join();
                    t2.join();
                } catch (Exception e) {
                    System.exit(1);
                }
                
                return f1.result + f2.result;
            }
        }
    }

    static class FibTask implements Runnable {
        int n;
        int depth;
        long result;
        
        FibTask(int n, int depth) {
            this.n = n;
            this.depth = depth;
        }
        
        public void run() {
            result = parFib(n, depth);
        }
    }
}
